#include <bits/stdc++.h>
using namespace std;

/*
2349. 设计数字容器系统
已解答
中等
相关标签
premium lock icon
相关企业
提示
设计一个数字容器系统，可以实现以下功能：

在系统中给定下标处 插入 或者 替换 一个数字。
返回 系统中给定数字的最小下标。
请你实现一个 NumberContainers 类：

NumberContainers() 初始化数字容器系统。
void change(int index, int number) 在下标 index 处填入 number 。如果该下标 index 处已经有数字了，那么用 number 替换该数字。
int find(int number) 返回给定数字 number 在系统中的最小下标。如果系统中没有 number ，那么返回 -1 。
 

示例：

输入：
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
输出：
[null, -1, null, null, null, null, 1, null, 2]

解释：
NumberContainers nc = new NumberContainers();
nc.find(10); // 没有数字 10 ，所以返回 -1 。
nc.change(2, 10); // 容器中下标为 2 处填入数字 10 。
nc.change(1, 10); // 容器中下标为 1 处填入数字 10 。
nc.change(3, 10); // 容器中下标为 3 处填入数字 10 。
nc.change(5, 10); // 容器中下标为 5 处填入数字 10 。
nc.find(10); // 数字 10 所在的下标为 1 ，2 ，3 和 5 。因为最小下标为 1 ，所以返回 1 。
nc.change(1, 20); // 容器中下标为 1 处填入数字 20 。注意，下标 1 处之前为 10 ，现在被替换为 20 。
nc.find(10); // 数字 10 所在下标为 2 ，3 和 5 。最小下标为 2 ，所以返回 2 。
 

提示：

1 <= index, number <= 109
调用 change 和 find 的 总次数 不超过 105 次。
*/

// 法一
class NumberContainers {
    // ct：下标 -> 该下标当前存储的最新数字（记录每个下标的实时值，用于判断堆中元素是否失效）
    unordered_map<int, int> ct;
    // mi：数字 -> 存储该数字下标的小顶堆（堆顶是「候选最小下标」，但需排除已失效的下标）
    // 采用小顶堆是为了天然保证堆顶为最小下标，无需额外排序
    unordered_map<int, priority_queue<int, vector<int>, greater<int>>> mi;

public:
    // 构造函数：初始化空映射，无额外操作
    NumberContainers() {}

    // 在下标index处填入/替换数字number（核心：采用「延迟删除」策略提升性能）
    void change(int index, int number) {
        // 1. 直接更新下标index的最新数字（覆盖旧值，无需立即处理旧数字的堆）
        ct[index] = number;
        // 2. 将当前下标index推入新数字number的小顶堆（即使该下标曾属于其他数字，也不立即删除旧堆中的记录）
        // 理由：堆无法高效删除中间元素，故将「删除失效元素」的操作延迟到find时处理，减少change的耗时
        mi[number].push(index);
    }

    // 返回数字number的最小下标，无则返回-1（核心：清理堆中失效元素，获取有效最小下标）
    int find(int number) {
        // 获取当前数字对应的小顶堆（若不存在则自动创建空堆，不影响后续判断）
        auto& q = mi[number];

        // 延迟删除：清理堆顶「失效的下标」（下标最新数字已不是当前number）
        // 循环条件：堆非空 + 堆顶下标对应的最新数字 != 当前查询的number（说明该下标已被替换，堆中记录失效）
        while (q.size() && ct[q.top()] != number) {
            q.pop(); // 弹出失效下标，直到堆顶为有效下标或堆空
        }

        // 堆空说明无有效下标，否则堆顶就是当前数字的最小有效下标
        return q.empty() ? -1 : q.top();
    }
};

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers* obj = new NumberContainers();
 * obj->change(index,number);
 * int param_2 = obj->find(number);
 */

// 法二
class NumberContainers {
private:
    // 下标 -> 对应的数字（用于快速获取某下标当前的数字，处理替换逻辑）
    unordered_map<int, int> idx_to_num;
    // 数字 -> 该数字所有下标的有序集合（set自动排序，begin()即为最小下标）
    unordered_map<int, set<int>> num_to_idxs;

public:
    NumberContainers() {
        
    }
    
    // 在下标index处填入/替换数字number
    void change(int index, int number) {
        // 旧数字存在 旧数字的下标集合中先删除index
        if (idx_to_num.count(index)) {
            int old = idx_to_num[index];
            num_to_idxs[old].erase(index);

            // 节约内存 集合为空的情况删除数字对应的key
            if (num_to_idxs[old].empty())   num_to_idxs.erase(old);
        }

        // 更新下标 对应的新数字
        idx_to_num[index] = number;
        // 进set自动升序
        num_to_idxs[number].insert(index);
    }
    
    // 返回数字number的最小下标，无则返回-1
    int find(int number) {
        // 检查数字是否存在，且对应的下标集合非空
        if (num_to_idxs.count(number) && !num_to_idxs[number].empty())       return *num_to_idxs[number].begin();  // set.begin()是最小下标
        return -1;  // 数字不存在或无下标
    }
};

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers* obj = new NumberContainers();
 * obj->change(index,number);
 * int param_2 = obj->find(number);
 */

// 法三
class NumberContainers {
public:
    // mpq：数字 -> 存储该数字下标的小顶堆（堆顶即最小下标，堆内元素均为有效下标）
    unordered_map<int, priority_queue<int, vector<int>, greater<int>>> mpq;
    // v：下标 -> 该下标当前对应的最新数字（记录下标实时值，用于判断是否需更新堆）
    unordered_map<int, int> v;

    // 构造函数：初始化两个映射（清空操作冗余但不影响，确保初始为空）
    NumberContainers() {
        mpq.clear();
        v.clear();
    }

    // 在下标index处填入/替换数字number（核心：主动清理旧堆失效元素，保证堆有效性）
    void change(int index, int number) {
        int curr = v[index]; // 获取下标index当前的旧数字
        if (curr == number) return; // 新旧数字相同，无需更新，直接返回

        // 步骤1：清理旧数字curr的堆——移除其中的当前下标index（避免残留失效下标）
        priority_queue<int, vector<int>, greater<int>> tmp;
        while (!mpq[curr].empty()) {
            if (mpq[curr].top() != index) { // 保留非当前index的有效下标
                tmp.push(mpq[curr].top());
            }
            mpq[curr].pop();
        }
        mpq[curr] = tmp; // 用筛选后的临时堆替换旧堆
        if (mpq[curr].empty()) mpq.erase(curr); // 旧堆空则删除键，节省内存

        // 步骤2：更新下标映射 + 加入新数字的堆
        v[index] = number; // 下标index绑定新数字
        mpq[number].push(index); // 新数字的堆加入当前下标
    }

    // 返回数字number的最小下标（堆已确保有效，直接取堆顶）
    int find(int number) {
        if (mpq.find(number) == mpq.end()) return -1; // 数字不存在，返回-1
        return mpq[number].top(); // 小顶堆堆顶即最小有效下标
    }
};

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers* obj = new NumberContainers();
 * obj->change(index,number);
 * int param_2 = obj->find(number);
 */
